
''
''
'' This file is part of FreeBASIC Regular Expressions Library
''
''


	'' CharClass type
	
	Type CharClass
		
		ClassName	As String
		Characters	As String
		
		Declare Constructor(n As String = "", c As String = "")
		
	End Type
	
	Constructor CharClass(n As String = "", c As String = "")
		
		ClassName = n
		Characters = c
		
	End Constructor
	
	DefineDynamicArrayType( CharClass )
	
	'' ----------
	
			
	'' Preprocessor type
	
	'
	'  Preprocessor is used to convert Extended Regular Expression (ERE) syntax
	'  to simplyfied syntax that is used by compiler
	'
	'  replacements that are made:
	'
	'	  A+				->		AA*   
	'
	'	  A{3}			->		AAA
	'
	'	  A{2,0}			->		AAA*
	'
	'	  A{0,3}			->		A?A?A?
	'
	'	  A{2,4}			->		AAA?A?
	'
	'	  [ABCDEF]		->		(A|B|C|D|E|F)
	'
	'	  [0-9]			->		(0|1|2|3|4|5|6|7|8|9)
	'
	'	  [^0-9]			->		(...|.|.|.|...)  (all characters except 0|1|2|3|4|5|6|7|8|9)
	'
	'	  [:lower:]		->		(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)
	'
	'		.				->		(...|.|.|.|...)	(all characters)
	'
	
	Type Preprocessor
		
		Public:
		
			Declare Constructor
			
			Declare Function Preprocess(ByRef Pattern As String, Multiline As Boolean, IgnoreCase As Boolean) As Boolean
			
			ErrorDescription	As String
			
			CharacterClass	As CharClassArray
				
		
		Private:
			
			caseSensitive	As Boolean
			
			source			As String
			position			As Integer
			lookahead		As String * 1
			
			charset			As String
			
			Declare Sub NextChar
			Declare Function ReadNumber As Integer
			Declare Function ReadHexNumber(length As Integer = 0) As Integer
			
			Declare Function RegExp(ByRef Result As String) As Boolean
			Declare Function Branch(ByRef Result As String) As Boolean
			Declare Function Piece(ByRef Result As String) As Boolean
			Declare Function Atom(ByRef Result As String) As Boolean
			Declare Function Repeat(ByRef Result As String) As Boolean
			Declare Function Item(ByRef Result As String) As Boolean
			Declare Function Literal(ByRef Result As String, InsideBrackets As Boolean = False) As Boolean
		
	End Type
	
	
	Constructor Preprocessor
		
		CharacterClass.Add Type<CharClass>("alnum", 	"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")
		CharacterClass.Add Type<CharClass>("alpha", 	"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")
		CharacterClass.Add Type<CharClass>("blank", 	!"\&h20\&h09")
		CharacterClass.Add Type<CharClass>("cntrl", 	!"\&h00\&h01\&h02\&h03\&h04\&h05\&h06\&h07\&h08\&h09\&h0a\&h0b\&h0c\&h0d\&h0e\&h0f\&h10\&h11\&h12\&h13\&h14\&h15\&h16\&h17\&h18\&h19\&h1a\&h1b\&h1c\&h1d\&h1e\&h1f\&h7f")
		CharacterClass.Add Type<CharClass>("digit", 	"0123456789")
		CharacterClass.Add Type<CharClass>("graph", 	"!#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~" + Chr(34))
		CharacterClass.Add Type<CharClass>("lower", 	"abcdefghijklmnopqrstuvwxyz")
		CharacterClass.Add Type<CharClass>("print", 	" !#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~" + Chr(34))
		CharacterClass.Add Type<CharClass>("punct", 	"-!#$%&'()*+,./:;<=>?@[\]_`{|}~" + Chr(34))
		CharacterClass.Add Type<CharClass>("space", 	!" \t\r\n\v\f")	
		CharacterClass.Add Type<CharClass>("upper", 	"ABCDEFGHIJKLMNOPQRSTUVWXYZ")
		CharacterClass.Add Type<CharClass>("xdigit",	"0123456789ABCDEFabcdef")
		
	End Constructor
	
	
	Function Preprocessor.Preprocess(ByRef Pattern As String, Multiline As Boolean, IgnoreCase As Boolean) As Boolean
		
		caseSensitive = Not IgnoreCase
		
		charset = ""
		
		For i As Integer = 1 To 255
			
			If (Not (Multiline AndAlso (i = 10 Or i = 13))) AndAlso _
				(Not (IgnoreCase AndAlso i >= Asc("A") AndAlso i <= Asc("Z"))) Then _
																								_
				charset += Chr(i)
				
		Next
		
		If IgnoreCase Then 
			source = LCase(source)
		Else
			source = Pattern
		EndIf
		
		position = 0
		
		NextChar
		
		Pattern = ""
		
		Return RegExp(Pattern)
		
	End Function
	
	
	Sub Preprocessor.NextChar
		
		Do
			position += 1
			
			If position > Len(source) Then
				lookahead = CHAR_EOF
			Else
				lookahead = Mid(source, position)
			EndIf
					
		Loop While InStr(lookahead, Any !"\&h20\&h09\&hA0") > 0
		
	End Sub
	
	'
	'  number ::= [0-9]+
	'
	Function Preprocessor.ReadNumber As Integer
		
		If InStr(lookahead, Any "0123456789") > 0 Then
			
			Dim As String number
			
			Do While InStr(lookahead, Any "0123456789") > 0
				
				number += lookahead
				
				position += 1
				
				If position > Len(source) Then
					lookahead = CHAR_EOF
				Else
					lookahead = Mid(source, position)
				EndIf
				 
			Loop
			
			Return ValInt(number)
		
		EndIf
		
		Return -1
		
	End Function
	
	
	'
	'  hex-number ::= [0-9a-fA-F]+
	'
	Function Preprocessor.ReadHexNumber(length As Integer = 0) As Integer
		
		If InStr(lookahead, Any "0123456789abcdefABCDEF") > 0 Then
			
			Dim As String number
			
			Do While InStr(lookahead, Any "0123456789abcdefABCDEF") > 0
				
				number += lookahead
				
				position += 1
				
				If position > Len(source) Then
					lookahead = CHAR_EOF
				Else
					lookahead = Mid(source, position)
				EndIf
				
				If Len(number) = length Then Exit Do
				
			Loop
			
			Return ValInt("&H" + number)
		
		EndIf
		
		Return -1
		
	End Function
	
	
	'
	'  regexp ::= branch
	'           | branch "|" regexp
	'
	Function Preprocessor.RegExp(ByRef Result As String) As Boolean
		
		If Not Branch(Result) Then Return False
			
		If lookahead = "|" Then
			
			Dim As String r
			
			NextChar
			
			Result += "|"
			
			If Not RegExp(r) Then Return False
			
			Result += r
			
		EndIf	
					
		Return True
		
	End Function
	
	
	'
	'  branch ::= piece
	'           | piece branch
	'
	Function Preprocessor.Branch(ByRef Result As String) As Boolean
		
		If Not Piece(Result) Then Return False
			
		If InStr(lookahead, Any "|)" + CHAR_EOF) <= 0 Then
			
			Dim As String r
		
			If Not Branch(r) Then Return False
			
			Result += r
			
		EndIf
		
		Return True
		
	End Function
	
	
	'
	'  piece ::= atom
	'          | atom repeat
	'
	Function Preprocessor.Piece(ByRef Result As String) As Boolean
		
		If Not Atom(Result) Then Return False
			
		If InStr(lookahead, Any "?*+{") > 0 Then
		
			If Not Repeat(Result) Then Return False
			
		EndIf
					
		Return True
		
	End Function
	
	'
	'  repeat ::= "*"
	'           | "+"
	'           | "?"
	'           | "{" [0-9]+ "," [0-9]+ "}"
	'           | "{" "," [0-9]+ "}"
	'           | "{" [0-9]+ "," "}"
	'           | "{" [0-9]+ "}"
	'
	Function Preprocessor.Repeat(ByRef Result As String) As Boolean
		
		Select Case As Const Asc(lookahead)
			
			Case Asc("*"), Asc("?")
				Result += lookahead
				NextChar
			
			Case Asc("+")
				Result += Result + "*"
				NextChar
			
			Case Asc("{")
				
				Dim As Integer min, max
				Dim As String r = Result 
				
				NextChar
				
				min = ReadNumber
				
				If lookahead = "," Then
					
					NextChar
					
					max = ReadNumber
					
					If lookahead <> "}" Then
						ErrorDescription = "Expected } at offset " + Str(position)
						Return False	
					EndIf
					
					NextChar
					
					If min <= 0 And max <= 0 Then
			
						Result += "*"
						
					Else
						
						Result = ""
						
						For i As Integer = 1 To min
							Result += r
						Next
						
						If min >= max Then
							
							Result += r + "*"
							
						Else
	
							If min > 0 Then max -= min
							
							For i As Integer = 1 To max
								Result += r + "?"
							Next
	
						EndIf
													
					EndIf
					
				ElseIf lookahead = "}" Then
					
					NextChar
					
					Result = ""
					
					For i As Integer = 1 To min
						Result += r
					Next
					
				Else
					ErrorDescription = "Expected , or } at offset " + Str(position)
					Return False
				EndIf  
			
		End Select
		
		Return True
		
	End Function
	
	'
	'  atom ::= "(" regexp ")"
	'         | brackets
	'         | "."
	'         | assertion
	'         | literal
	'
	'  brackets ::= "[" item+ "]"
	'             | "[^" item+ "]"
	'
	Function Preprocessor.Atom(ByRef Result As String) As Boolean
		
		If lookahead = "(" Then
			
			NextChar
			
			If Not RegExp(Result) Then Return False
			
			If lookahead <> ")" Then
				ErrorDescription = "Expected ) at offset " + Str(position) 
			EndIf
			
			NextChar
			
			Result = "(" + Result + ")"
		
		ElseIf lookahead = "[" And Mid(source, position + 1, 1) <> ":" Then
			
			NextChar
			
			Dim r As String
			
			If lookahead = "^" Then
				
				Dim As String exclude
				
				NextChar
				
				Do
					If Not Item(exclude) Then Return False
					r += exclude
					If lookahead = CHAR_EOF Then
						ErrorDescription = "Unexpected end of expression"
						Return False
					EndIf
				Loop While lookahead <> "]"
				
				If Len(exclude) = 0 Then
					ErrorDescription = "Unexpected ] at offset " + Str(position)
					Return False
				EndIf
				
				exclude = r
				r = ""
				
				For i As Integer = 1 To Len(charset)
					If InStr(Mid(charset, i, 1), Any exclude) = 0 Then
						r += Mid(charset, i, 1)
					EndIf
				Next
				
			Else
				
				Dim As String char
				
				Do
					If Not Item(char) Then Return False
					r += char
					If lookahead = CHAR_EOF Then
						ErrorDescription = "Unexpected end of expression"
						Return False
					EndIf
				Loop While lookahead <> "]"
				
				If Len(r) = 0 Then
					ErrorDescription = "Unexpected ] at offset " + Str(position)
					Return False
				EndIf
				
			EndIf
			
			If lookahead <> "]" Then
				ErrorDescription = "Expected ] at offset " + Str(position)
				Return False
			EndIf
			
			' remove duplicates
			Dim As String copy
			
			For i As Integer = 0 To Len(r)
				If InStr(copy, Mid(r, i, 1)) = 0 Then copy += Mid(r, i, 1)
			Next
			
			r = copy
			' ---
			
			NextChar
			
			Result = "("
			
			For i As Integer = 1 To Len(r)
				Result += Mid(r, i, 1)
				If i < Len(r) Then Result += "|"
			Next
			
			Result += ")"
		
		ElseIf lookahead = "." Then
			
			NextChar
			
			Result = "("
			
			For i As Integer = 1 To Len(charset)
				Result += Mid(charset, i, 1)
				If i < Len(charset) Then Result += "|"
			Next
			
			Result += ")"
		
		ElseIf lookahead = "^" Or lookahead = "$" Then
			
			Result = lookahead
			
			NextChar
		
		Else
			
			Return Literal(Result)
			
		EndIf
		
		Return True
		
	End Function
	
	
	'
	'  item ::= literal
	'         | literal "-" literal
	'
	Function Preprocessor.Item(ByRef Result As String) As Boolean
		
		Dim As String r1, r2
		
		If Not Literal(r1, True) Then Return False
		
		Result += r1
		
		If lookahead = "-" Then
		
			NextChar
		
			If lookahead = "]" Then
				
				Result += "-"
			
			ElseIf lookahead = CHAR_EOF Then
				
				ErrorDescription = "Unexpected end of expression"
				Return False
				
			Else
		
				If Not Literal(r2, True) Then Return False
				
				For i As Integer = Asc(Right(r1, 1)) + 1 To Asc(Left(r2, 1)) - 1
					Result += Chr(i)						
				Next 
				
				Result += r2
				
			EndIf
			   			
		EndIf
	
		Return True
		
	End Function
	
	'
	'  literal ::= <ordinary character>
	'            | "\x" [1-9a-fA-F]{2}
	'            | "\" escape-char
	'            | "[:" [a-zA-Z0-9]+ ":]"
	'
	'  escape-char ::= "\" | "." | "[" | "]" | "-" | "{" | "}" | "(" | "^"
	'                | ")" | "|" | "+" | "*" | "?" | "n" | "r" | "t" | "$"
	'
	Function Preprocessor.Literal(ByRef Result As String, InsideBrackets As Boolean = False) As Boolean
		
		If lookahead = "\" Then
			
			NextChar
			
			If lookahead = "x" Then
				
				NextChar
				
				Dim As Integer code = ReadHexNumber(2)
				
				If code < 0 Then
					ErrorDescription = "Expected hexadecimal digit as offset " + Str(position)
					Return False
				EndIf
				
				If InStr(Chr(code), Any !"\&h20\&h09\&hA0\\()|*?$^") > 0 Then
					Result = "\x" + Right("00" + Hex(code), 2)
				Else
					Result = Chr(code) 
				EndIf
				
			ElseIf InStr(lookahead, Any ".[]-{}+nrt") Then
				
				Result = lookahead
				NextChar
			
			ElseIf InStr(lookahead, Any "\()|*?$^") Then
				
				Result = "\" + lookahead
				NextChar
			
			Else
				
				ErrorDescription = "Invalid escape sequence at offset " + Str(position)
				Return False
			
			EndIf
			
		ElseIf lookahead = "[" And Mid(source, position + 1, 1) = ":" Then
			
			Dim As String className
			
			NextChar
			NextChar
			
			Do While InStr(lookahead, Any "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789") > 0
	
				className += lookahead
				NextChar      			
				
			Loop
			
			If lookahead <> ":" Then
				ErrorDescription = "Expected :] at offset " + Str(position)
				Return False
			EndIf
			
			NextChar
			
			If lookahead <> "]" Then
				ErrorDescription = "Expected :] at offset " + Str(position)
				Return False
			EndIf
			
			NextChar
			
			If Len(className) = 0 Then
				ErrorDescription = "Expected class name at offset " + Str(position - 2)
				Return False
			EndIf
			
			Dim As String chars
			
			className = LCase(className)
			
			For i As Integer = 0 To CharacterClass.ItemCount - 1
				If className = LCase(CharacterClass.Item(i).ClassName) Then
					chars = CharacterClass.Item(i).Characters
					Exit For
				EndIf	
			Next
			
			If Len(chars) = 0 Then
				ErrorDescription = "Unknown class name '" + className + "' at offset " + Str(position - Len(className) - 2)
				Return False
			EndIf
			
			If Not caseSensitive Then chars = LCase(chars)
			
			If InsideBrackets Then
				
				Result = chars
				
			Else
				
				Result = "("
				
				For i As Integer = 1 To Len(chars)
					Result += Mid(chars, i, 1)
					If i < Len(chars) Then Result += "|"
				Next
				
				Result += ")"
				
			EndIf
			
		ElseIf InStr(lookahead, Any "[](){}+*?") = 0 Then 
			
			Result = lookahead
			
			NextChar
			
		EndIf	
		
		Return True
		
	End Function